{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "40a2d599",
   "metadata": {},
   "source": [
    "# 抽象语法树AST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f2f1554f",
   "metadata": {},
   "outputs": [],
   "source": [
    "INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = 'INTERGER', 'PLUS', 'MINUS', 'MUL', 'DIV', 'LPAREN', 'RPAREN', 'EOF'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "45fb3e98",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Token:\n",
    "    \"\"\"记号类\n",
    "    \"\"\"\n",
    "    def __init__(self, value_type, value):\n",
    "        self.value_type = value_type # 记号的类型\n",
    "        self.value = value # 记号的值\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\"重写查看记号内容的方法\"\"\"\n",
    "        return f\"Token({self.value_type}, {self.value})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return self.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bc0cbf7c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Lexer:\n",
    "    \"\"\"解释器类\n",
    "    \"\"\"\n",
    "    def __init__(self, text):\n",
    "        self.text = text\n",
    "        self.position = 0\n",
    "        self.current_char = self.text[self.position]\n",
    "    \n",
    "    def error(self):\n",
    "        raise Exception('警告：错误的输入内容！')\n",
    "    \n",
    "    def advance(self):\n",
    "        \"\"\"定义获取下一个字符的方法\n",
    "        \"\"\"\n",
    "        self.position += 1\n",
    "        if self.position >= len(self.text):\n",
    "            self.current_char = None\n",
    "        else:\n",
    "            self.current_char = self.text[self.position]\n",
    "    \n",
    "    def skip_whitespace(self):\n",
    "        \"\"\"定义跳过空格的方法\n",
    "        \"\"\"\n",
    "        while self.current_char is not None and self.current_char.isspace():\n",
    "            self.advance()\n",
    "    \n",
    "    def long_integer(self):\n",
    "        result = ''\n",
    "        while self.current_char is not None and self.current_char.isdigit():\n",
    "            result += self.current_char\n",
    "            self.advance()\n",
    "        return int(result)\n",
    "            \n",
    "    def get_next_token(self):\n",
    "        while self.current_char is not None:\n",
    "            if self.current_char.isspace():\n",
    "                self.skip_whitespace()\n",
    "                continue\n",
    "            if self.current_char.isdigit():\n",
    "                token = Token(INTEGER, self.long_integer())\n",
    "                return token\n",
    "            if self.current_char == '+':\n",
    "                token = Token(PLUS, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            if self.current_char == '-':\n",
    "                token = Token(MINUS, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            if self.current_char == '*':\n",
    "                token = Token(MUL, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            if self.current_char == '/':\n",
    "                token = Token(DIV, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            if self.current_char == '(':\n",
    "                token = Token(LPAREN, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            if self.current_char == ')':\n",
    "                token = Token(RPAREN, self.current_char)\n",
    "                self.advance()\n",
    "                return token\n",
    "            self.error()\n",
    "        return Token(EOF, None)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f397642b",
   "metadata": {},
   "source": [
    "# 支持括号嵌套的文法\n",
    "\n",
    "关键点在于一个括号以内部的表达式的处理，当作一个基本单位去处理\n",
    "factor是基本单位，表示整数或者带括号的表达式；\n",
    "term表示乘除法；\n",
    "expr表示加减法\n",
    "文法从上到下，表达优先级从低到高\n",
    "```\n",
    "expr: term((PLUS|MINUS)term)*\n",
    "term: factor((MUL|DIV)factor)*\n",
    "factor: INTEGER|LPAREN expr RPAREN\n",
    "```\n",
    "新的文法中，基本单位不再仅仅是整数，而是新增了一个LPAREN expr RPAREN。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f67f7405",
   "metadata": {},
   "outputs": [],
   "source": [
    "class AST:\n",
    "    \"\"\"抽象语法树基类\n",
    "    \"\"\"\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a710b81e",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Num(AST):\n",
    "    \"\"\"数字节点\n",
    "    \"\"\"\n",
    "    def __init__(self, token):\n",
    "        self.token = token\n",
    "        self.value = token.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7e91cc2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinOp(AST):\n",
    "    \"\"\"二元运算符节点\n",
    "    \"\"\"\n",
    "    def __init__(self, left, op, right):\n",
    "        self.left = left\n",
    "        self.token = self.op = op\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "46bf2776",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Parser:\n",
    "    \"\"\"语法解析器\n",
    "    \"\"\"\n",
    "    def __init__(self, lexer):\n",
    "        self.lexer = lexer\n",
    "        self.current_token = lexer.get_next_token()\n",
    "    \n",
    "    def eat(self, token_type):\n",
    "        print(self.current_token)\n",
    "        if self.current_token.value_type == token_type:\n",
    "            if token_type != EOF:\n",
    "                self.current_token = self.lexer.get_next_token()\n",
    "        else:\n",
    "            self.error()\n",
    "    \n",
    "    def factor(self):\n",
    "        token = self.current_token\n",
    "        if token.value_type == INTEGER:\n",
    "            self.eat(INTEGER)\n",
    "            return Num(token)\n",
    "        elif token.value_type == LPAREN:\n",
    "            self.eat(LPAREN)\n",
    "            node = self.expr()\n",
    "            self.eat(RPAREN)\n",
    "            return node\n",
    "    \n",
    "    def term(self):\n",
    "        \"\"\"乘除法\n",
    "        \"\"\"\n",
    "        node = self.factor()\n",
    "        \n",
    "        while self.current_token.value_type in (MUL, DIV):\n",
    "            token = self.current_token\n",
    "            if token.value_type == MUL:\n",
    "                self.eat(MUL)\n",
    "            if self.current_token.value_type == DIV:\n",
    "                self.eat(DIV)\n",
    "            node = BinOp(left=node, op=token, right=self.factor())\n",
    "        return node\n",
    "\n",
    "    \n",
    "    def expr(self):\n",
    "        \"\"\"加减法\n",
    "        \"\"\"\n",
    "        node = self.term()\n",
    "        \n",
    "        while self.current_token.value_type in (PLUS, MINUS):\n",
    "            token = self.current_token\n",
    "            if token.value_type == PLUS:\n",
    "                self.eat(PLUS)\n",
    "            if token.value_type == MINUS:\n",
    "                self.eat(MINUS)\n",
    "            node = BinOp(left=node, op=token, right=self.term())\n",
    "        return node\n",
    "    \n",
    "    def parse(self):\n",
    "        return self.expr()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed39964b",
   "metadata": {},
   "source": [
    "# 应用AST结构\n",
    "需要使用到访问者模式，后续遍历AST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2a7e951a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeVisitor:\n",
    "    \"\"\"定义节点访问器类\n",
    "    \"\"\"\n",
    "    def visit(self, node):\n",
    "        method_name = 'visit_' + type(node).__name__\n",
    "        # print(f\"visitor = {method_name}\")\n",
    "        visitor = getattr(self, method_name, self.generic_visitor)\n",
    "        return visitor(node)\n",
    "    \n",
    "    def generic_visitor(self, node):\n",
    "        raise Exception(f\"未找到visit_{type(node).__name__}()方法\")\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "15e11d70",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Interpreter(NodeVisitor):\n",
    "    \"\"\"解释器类\n",
    "    \"\"\"\n",
    "    def __init__(self, parser):\n",
    "        self.parser = parser\n",
    "    \n",
    "    def visit_BinOp(self, node):\n",
    "        if node.op.value_type == PLUS:\n",
    "            return self.visit(node.left) + self.visit(node.right)\n",
    "        elif node.op.value_type == MINUS:\n",
    "            return self.visit(node.left) - self.visit(node.right)\n",
    "        elif node.op.value_type == MUL:\n",
    "            return self.visit(node.left) * self.visit(node.right)\n",
    "        elif node.op.value_type == DIV:\n",
    "            return self.visit(node.left) / self.visit(node.right)\n",
    "    \n",
    "    def visit_Num(self, node):\n",
    "        return node.value\n",
    "    \n",
    "    def interpret(self):\n",
    "        tree = self.parser.parse()\n",
    "        return self.visit(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d6bb9be0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "    while True:\n",
    "        text = input(\"输入算式：\")\n",
    "        if text == 'q':\n",
    "            break\n",
    "        lexer = Lexer(text)\n",
    "        parser = Parser(lexer)\n",
    "        interpreter = Interpreter(parser)\n",
    "        result = interpreter.interpret()\n",
    "        print(text, \"=\", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "13d63f4e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输入算式：q\n"
     ]
    }
   ],
   "source": [
    "main()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
